package com.clstu.algrithm;

/**
 * 分治算法之 --- 汉诺塔
 */
public class HanoiTower {
    private static int count = 0;
    public static void main(String[] args) {
        hanoiTower(8,'A','B','C');
    }
    //编写方法,解决汉诺塔问题
    //将num个盘 借助b柱子从a柱子移动到c柱子 ,打印它的步骤
    public static void hanoiTower(int num,char a,char b,char c){
        //思路分析:
        //1.将num-1个盘当做整体从a--->b
        //2.将最大的盘移从a--->c
        //3.在将num-1个盘从b--->c
        //如果到最后(只有一个盘)
        if(num==1){
            System.out.println("第"+(++count)+"步: "+a+"------>"+c);
            return;
        }
        //否则就分治求解
        //1.mun-1个盘移动到a--->b
        hanoiTower(num-1,a,c,b);
        //2.最大的盘移动a--->c
        System.out.println("第"+(++count)+"步: "+a+"------>"+c);
        //3.在将num-1个盘从b--->c
        hanoiTower(num-1,b,a,c);
    }
}
